// len = 2^x >= max(sz(a),sz(b))*2
namespace FFT{
    void fft(vir *F,int len,int o){
        int j = 0 , k , h;
        rep(i,0,len-1){
            if(i < j) swap(F[i] , F[j]);
            for(k=len;j>=(k>>=1);j&=~k);  j|=k;
        }
        for(h=1;h<len;h<<=1){
            vir wn(cos(pi*o/h),sin(pi*o/h));
            for(j=0;j<len;j+=h<<1){
                vir w(1.);
                for(k=j;k<j+h;++k,w=w*wn){
                    vir b = w*F[k+h];
                    F[k+h] = F[k]-b , F[k] = F[k]+b;
                }
            }
        }
        if(o == -1) rep(i,0,len) F[i] = F[i]/(db)len;
    }
    void mult(vir *a,vir *b,int len){
        fft(a,len,1);fft(b,len,1);
        rep(i,0,len) a[i] = a[i] * b[i];
        fft(a,len,-1);
    }
}

